The implementation of an array multiplier circuit is an important aspect of many modern arithmetic systems. A rectangular aspect ratio array multiplier circuit is disclosed in U.S. Pat. No. 5,144,576, issued on Sep. 1, 1992 entitled "RECTANGULAR ASPECT RATIO SIGNED DIGIT MULTIPLIER" and assigned to the assignee of the present application, the disclosure of which is hereby incorporated by reference. The use of rectangular aspect ratio multipliers allows for the formation of short by long products to expedite the performance of a variety of arithmetic functions such as the square root and division operations described in the previously cited application. The calculation of the product of two full-length operands in a rectangular aspect ratio multiplier involves multiple iterations or passes through the array multiplier.
Most multiplier circuits involve some sort of Booth recoding to limit the required digit set used within the multiplier array. The conventional Booth recoding requires a digit set comprising the digits 2, 1, 0, -1, and -2. This digit set dictates that the partial product generators within the multiplier must have the capability to shift and negate one of the operands of the multiplication operation prior to addition of the partial products within the adder tree comprising the multiplier array.
When utilizing twos complement numbers, an operand is negated by forming the NOT or inverse of the operand and then adding "1" in the least significant bit position. Obtaining the NOT or inverse of the number is not difficult within an adder tree. Adding a "1" in the least significant bit position is a difficult operation because it involves using a full level of an adder circuit to account for any potential carry ripple through the length of a partial product formed using the negated operand. Full adder circuits result in significant propagation delays within the array multiplier and, as such, circuit designers strive to limit the levels of adders required in an array multiplier.
Accordingly, a need has arisen for a system and method for negating an operand in an array multiplier which allows for multiple passes through the array to form a full length product of two operands.